﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>


//非递归版本的归并排序的实现
//递归版本很像树的后续遍历，由于归并的两数组必须为有序的；所以得从单个数据一个一个来；
//不使用递归，可以从下标规律的角度下手
//可以通过控制Gap 来控制待归并数组中的数组个数;当gap >=n 的时候，循环结束
//归并的核心，将两个有序的序列合并成一个有序的序列
void MergeSortNonR(int* a, int n)
{
	//首先是需要创建一个数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//gap 是成倍增加的
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i+= 2*gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap + gap - 1;
			//有序列可能没有，或者个数没有gap 个
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = 0;
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			//没有完的
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//将tmp 中的数据放回原数组
			memcpy(a + i, tmp, sizeof(int) * (end2 - i + 1));
		}
		//走完一遍gap 变一下
		gap *= 2;
	}
}

void Print(int *a , int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
//归并排序既可以归为内排序，也可以归为内排序
//即指的是硬盘、磁盘；当数据量很多的时候就不能将数据全部放在内存中进行计算；
//此时是不能使用内排序进行排序的；因为内排序的思想是要访问内存当中的一个下标位置，磁盘
//当中能够支持我们去访问特定位置的数据，但是不断地变化会使得性能很慢
//可以使用归并排序，因为归并排序的思想是不需要进行下标位置的访问；
//我们可以将大文件分为一个一个的小文件，将小文件中的数据均排完序以后再进行归并排序；
//但是这中操作无法知道究竟要用多少个小文件来存放大文件中的数据；不好处理；
//另一种方法就是将大文件中的数据读取n个数据放入两个小文件中，两个小文件归并为一个文件
//然后再读取n个数据放入fail2 文件中，再归并……
//造数据
void CreatNDate()
{
	//数据个数
	int n = 1000000;
	//设置随机种子
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	//明天考六级，没时间写了 - 早上又摸起来写了
	//打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	//将随机数放到文件中
	for (int i = 0; i < n; i++)
	{
		int x = rand() + i;
		fprintf(fin, "%d\n", x);//写入的时候加个\n 便可以
		//将数据写入文件中可以用fread fwrite 等，但这些写完以后许哟啊将整形转文字，非常麻烦；在文件中均是以字符串的形式存储数据的

	}
	//关闭文件
	fclose(fin);
}

int int_compare(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

//首先是在主文件流 fin 中读取n个数据之后放入 file1 之中；
//然后是再读取n个数据放到file2 之中；
//频繁地打开文件关闭文件，需要控制文件指针，不太好操作
//在读文件的时候其文件指针是自动往后走的；
//然后再对file1 和 fil2 进行归并排序放到文件mfile 中；排完以后再将file1 和 file2 删除，将mfile 重命名为file1
// 再读取n 个数据放到file2 之中；重复上述操作
int ReadNDateSortToFile(FILE* fout , int n , const char* file)
{
	//需要利用数组存放从文件中读取的数据，排完序之后才会放入文件file1 之中
	int x = 0;
	int* arr = (int*)malloc(sizeof(int) * n);
	if (arr == NULL)
	{
		perror("malloc fail 1");
		exit(-1);
	}

	//从主文件中读取n个数据
	int j = 0;
	for (int i = 0; i  < n; i++)
	{
		//需要再增加一个判断；可能不会读到n个数据，一旦读取结束循环便停止
		if(fscanf(fout, "%d", &x) == EOF)
			break;
		//将数据放到数组中
		arr[j++] = x;
	}
	//也有可能一个数据都没有读到
	//那么就没有必要排序了
	if (j == 0)//j 代表着待排序数据的个数
	{
		free(arr);
		return 0;
	}
	//排序，可以直接使用C语言库中的qsort
	qsort(arr, j, sizeof(int), int_compare);
	
	//打开文件file  ,将arr 数组中有序的数据放入文件file 之中；
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		//在退出前记得释放动态开辟的空间
		free(arr);
		perror("fopen fail 2");
		exit(-1);
	}
	//写回
	for (int i = 0; i < j; i++)
	{
		fprintf(fin, "%d\n", arr[i]);
	}
	//释放动态开辟的空间、关闭文件
	free(arr);
	arr = NULL;
	fclose(fin);

	return j;//返回读取到的数据的个数
}
//将文件归并
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
	//打开file1 
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		perror("fopen fail 3");
		exit(-1);
	}
	//打开file2 
	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		perror("fopen fail 4");
		exit(-1);
	}
	//打开mfile 
	FILE* fin = fopen(mfile, "w");
	if (fin == NULL)
	{
		perror("fopen fail 5");
		exit(-1);
	}
	//将file1 与 file2 进行归并
	//将从file1 中读取的数据放到x1 中，将从file2 中读取的数据放到x2 中
	int x1 = 0;
	int x2 = 0;
	//file1 与 file2 中数据de个数可能不一样，一旦有一个读取结束便会停止
	int ret1 = fscanf(fout1, "%d", &x1);
	int ret2 = fscanf(fout2, "%d", &x2);
	while (ret1 != EOF && ret2 != EOF)
	{
		if (x1 < x2)
		{
			fprintf(fin, "%d\n", x1);
			ret1 = fscanf(fout1, "%d", &x1);
		}
		else
		{
			fprintf(fin, "%d\n", x2);
			ret2 = fscanf(fout2, "%d", &x2);
		}
	}
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", x1);
		ret1 = fscanf(fout1, "%d", &x1);
	}
	while (ret2 !=  EOF)
	{
		fprintf(fin, "%d\n", x2);
		ret2 = fscanf(fout2, "%d", &x2);
	}

	//关闭文件
	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}
void Test2()
{
	//文件
	const char* file1 = "file1.txt";
	const char* file2 = "file2.txt";
	const char* mfile = "mfile.txt";

	//提前打开主文件
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen fail 6");
		exit(-1);
	}  

	//一次读取的数据个数
	int n = 100000;
	//从主文件读取n个数据放到fail1 file2 之中
	ReadNDateSortToFile(fout, n, file1);
	ReadNDateSortToFile(fout, n, file2);

	//归并的逻辑
	while (1)
	{
		MergeFile(file1, file2, mfile);

		//销毁file1 file2
		remove(file1);
		remove(file2);

		//将mfile 改名为 file1
		int result = rename(mfile,file1);

		//再去主文件中读取数据放到file2 中
		int m = 0;//m 获取读到的数据个数
		if ((m = ReadNDateSortToFile(fout, n, file2)) == 0)
			break;//没有读到数据，便结束
	}
}

void Test1()
{
	int arr[] = { 10,9,89,23,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	Print(arr, sz - 1);
	MergeSortNonR(arr, sz);
	Print(arr, sz - 1);
}

int main()
{
	//Test1();
	//CreatNDate();

	Test2();
	return 0;
}
